Міністерство Освіти і Науки України Національний Університет “Львівська Політехніка”
Кафедра ЕОМ Елементи теорії графів Методичні вказівкидо практичних занять та самостійної роботи з курсу “Дискретна математика”для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” Затвердженона засіданні кафедриЕлектронних Обчислювальних МашинПротокол № 6 від 21 січня 2003 року Львів – 2003  Елементи теорії графів : Методичні вказівки до практичних занять та самостійної роботи з курсу “Дискретна математика” для студентів базового напрямку 6.0915 “Комп’ютерна інженерія” / Укладачі: І. Мороз, Р. Попович – Львів: Національний університет “Львівська політехніка”, 2003, 19 с. Укладачі: Р. Попович, к.т.н., доцент І. Мороз, асистент Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри ЕОМ Рецензенти: Ємець В. Ф., професор кафедри ЕОМ, д. фіз.-мат. н. Юрчак І. Ю., доцент кафедри САПР, к. т. н. Вступ Зародження теорії графів пов’язують з роботою Ейлера (1736 р.) про Кенігсберзькі мости. Який знайшов критерії існування в графі спеціального маршруту, так званого ейлеревого циклу. Тривалий час цей результат залишався єдиним у теорії графів. Нові результати були отримані лише в XIX ст. в роботах Кіргофа та Келі. Хоча теорія графів виникла більше двох століть тому, її інтенсивний розвиток припадає лише на останні 50-60 років. Цей розвиток завдячує широкому застосуванню графів в теорії автоматів, теорії проектування, економіці, хімії, біології та ін. Теорія графів, як розділ дискретної математики, з успіхом використовується у задачах керування виробництвом і проектування мереж ЕОМ, при розробці сучасних електронних модулів і при проектуванні фізичних систем, при розв’язуванні задач генетики і вирішенні проблем автоматизованого управління (САПР). Теорія графів є основою математичного забезпечення сучасних систем обробки інформації у прикладній теорії алгоритмів та в інших галузях науки і техніки. Одним з прикладів ефективного застосування теорії графів в сучасних інформаційних системах є кодування інформації при передачі через канал зв’язку. При цьому ставиться вимога забезпечити виправлення помилок, які виникають внаслідок фізичних завад у каналах зв’язку або пристроях зберігання інформації. Одним з кращих алгоритмів який вирішує дану задачу є алгоритм Вітербі, в основі якого лежить алгоритм пошуку оптимального шляху, що є предметом досліджень в теорії графів. Далі розглядатимемо деякі елементи теорії графів, які мають загальну форму та можуть бути застосовані при дослідженні об’єктів та систем довільної природи. 1. Основні поняття і операції 1.1. Визначення графу Предметом перших задач теорії графів були конфігурації, які складаються з точок і ліній, які їх з’єднують. При цьому несуттєво, прямі ці лінії або вони є криволінійними дугами. Важливо лише те, що вони з’єднують дані точки. Визначення. Розглянемо множину V, яка складається з точок, частина яких з’єднана між собою. Назвемо V множиною вершин, а об’єкт v ( V - вершиною. Граф G = G(V) з множиною вершин V - це деяка сукупність пар вигляду e = (a, b), де a, b ( V вказують, які пари вершин з’єднані між собою. Відповідно до геометричних уявлень про граф кожна така пара (a, b) називається ребром графу, а „а” і „b” – кінцями ребра. З іншого боку, оскільки e = (a, b) ( V ( V, то граф G(V) ( V ( V. Визначення. Якщо у визначенні ребра графу не брати до уваги послідовність його кінців, тобто вважати, що e = (a, b) = (b, a), то говорять, що e – неорієнтоване ребро. В протилежному випадку e = (a, b) - орієнтоване ребро, в якому „а” – початкова вершина, а „b” – кінцева. Визначення. Якщо e = (a, b), то говорять, що ребро e інцидентне вершинам „а” і „b”, а вершини „а” і „b” інцидентні ребру e. 1.2. Зображення графів Визначення. Граф G називається неорієнтованим, якщо кожне його ребро є неорієнтованим. Граф G називається орієнтованим, якщо кожне його ребро є орієнтованим.
Рис. 1. На рис. 1.а, б, в, е зображені деякі неорієнтовані графи, а на рис. 1.г, д – деякі орієнт...